#include "BinaryTree.h"

struct TreeNode
{
    TreeNode(const int &element) : data(element)
    {
        left = right = nullptr;
    }
    int data; // 数据域
    TreeNode *left;
    TreeNode *right;
};

TreeNode *root = nullptr;

const int SIZE = 100;
TreeNode *nodes[SIZE] = {nullptr};

void SelectTwoMin(int size, int &min1, int &min2)
{
    min1 = min2 = -1;
    for (int i = 0; i < size; i++)
    {
        if (nodes[i])
        {
            if (min1 == -1 || nodes[i]->data < nodes[min1]->data)         
            {
                min2 = min1;
                min1 = i;
            }
            else if (min2 == -1 || nodes[i]->data < nodes[min2]->data)
            {
                min2 = i;
            }
        }
    }
}

void BuildHuffmanTree(int *a, int size)
{
    for (int i = 0; i < size; i++)
    {
        nodes[i] = new TreeNode(a[i]); // 把数组变成树的结点
    }
    for (int i = 0; i < size - 1; i++)
    {
        int min1, min2; // 最小的两个结点
        SelectTwoMin(size, min1, min2);
        TreeNode *newnode = new TreeNode(nodes[min1]->data + nodes[min2]->data);
        newnode->left = nodes[min1];
        newnode->right = nodes[min2];

        nodes[min1] = newnode;
        nodes[min2] = nullptr;
    }

    for (int i = 0; i < size; i++)
        if (nodes[i])
        {
            root = nodes[i];
            break;
        }
}

void PrevTravel(TreeNode *node)
{
    if (node == nullptr)
        return;
    std::cout << node->data << " ";
    PrevTravel(node->left);
    PrevTravel(node->right);
}

void MidTravel(TreeNode *node)
{
    if (node == nullptr)
        return;

    MidTravel(node->left);
    std::cout << node->data << " ";
    MidTravel(node->right);
}

int main()
{
    BinaryTree t;
    int a[] = {5, 9, 12, 13, 16, 45};
    BuildHuffmanTree(a, 6);
    PrevTravel(root);
    std::cout << std::endl;
    MidTravel(root);
    std::cout << std::endl;

    // for(int i = 0;i < 6;i++)
    //     t.Insert(a[i]);
    // t.Remove(4);
    // t.show();
    // t.Remove(6);
    // t.show();
    // std::cout<<(t.Find(2) ? "zhaodaole" : "meizhaodao")<<std::endl;
    // int *p = t.Find(4);
    // if(p)
    //     std::cout<<"找到了："<<*p<<std::endl;
    // else
    //     std::cout<<"没找到"<<std::endl;
    
    return 0;
}
